1. Field of the Invention
One or more embodiments of the present invention relate to a mobile robot, and more particularly, to a method, medium, and system reducing the computational complexity of a Simultaneous Localization And Mapping (SLAM) algorithm applied to mobile robots.
2. Description of the Related Art
Robots or robotic devices were originally developed for industrial purposes and have been widely used for factory automation and for performing various functions in hazardous or extreme environments. Nowadays, robotics has evolved from the field of state-of-the-art space robots to the field of human-friendly home robots. In addition, robots have been proposed for replacing conventional medical equipment by being injected into the human body and repairing tissue that might not have been otherwise repaired. Thus, with recent achievements in the robotics field, robotics has moved into the limelight of the world in anticipation that robotics, as one of the most advanced fields of science, will increasingly replace other fields of science, such as Internet-based information technology and biotechnology.
In recent years, home mobile robots such as cleaning robots have been widely commercialized, so mobile robots are becoming more and more commonplace in people's daily lives.
In this regard, in robotics, localization techniques refer to processes by which a robot determines its position with respect to its surroundings. For example, in a “pure” localization system, the robot is provided with a map of its surroundings. Such “pure” localization systems are disadvantageous because generating a map via manual techniques is a relatively difficult, labor-intensive, and specialized task. Moreover, many environments are not static. For example, the rearranging of furniture in a room can render a preexisting map unusable. As a result, maps in pure localization systems are subject to relatively frequent and costly updates so that the map accurately represents its surroundings.
Therefore, it is desirable to develop localization techniques that are capable of planning the path of movement of a mobile robot and dynamically creating a map by determining the absolute position of the mobile robot based on a variation in the relative position of the mobile robot with respect to the surroundings of the mobile robot and one or more feature points of the surroundings of the mobile robot, even when no spatial information regarding the surroundings of the mobile robot is provided.
In the meantime, one of the most widely used techniques for determining the absolute position of a mobile robot based on the surroundings of the mobile robot and the relative position of the mobile robot with respect to the surroundings of the mobile robot is Simultaneous Localization And Mapping (SLAM). According to SLAM, even when a mobile robot does not have any spatial information (i.e., map information) regarding its surroundings, it still can extract one or more feature points with reference to distance data obtained using ultrasound waves, laser beams, or image data obtained using a camera, for example, and configure map information based on the extracted feature point. Then, the mobile robot can determine its position based on the configured map information.
Kalman filters are generally used to determine the pose of a mobile robot based on one or more feature points. However, pose estimation methods that involve the use of Kalman filters can be effective only when the distribution of estimated pose errors follow a Gaussian distribution. As part of the effort to address this problem, it has been suggested to use a pose estimation technique that extracts a number of samples regarding position estimates and determines an optimum pose of an object using the probability of each of the extracted samples even when the distribution of estimated pose errors does not follow a Gaussian distribution, i.e., a particle filter technique.
An example of such a particle filter technique is set forth in U.S. Pat. No. 7,015,831, which discusses incrementally updating the pose of a mobile device using visual SLAM techniques, and particularly, to a SLAM technique using a particle filter. To implement this technique, U.S. Pat. No. 7,015,831 sets forth using a plurality of sensors (i.e., odometer and a camera) using two particle sets.
However, such a SLAM technique using a particle filter generally requires a considerable number of samples, thereby increasing the amount of computation and making it difficult for a mobile robot to determine the pose of the mobile robot when the mobile robot moves from one place to another. Therefore, a particle filter-based SLAM technique capable of reducing the amount of computation and thus enabling real-time determination of the pose of a mobile robot is desired.